home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 3029 < prev    next >
Encoding:
Text File  |  1996-08-05  |  1.6 KB  |  36 lines
  1. Newsgroups: comp.lang.c
  2. Path: cwi.nl!dik
  3. From: dik@cwi.nl (Dik T. Winter)
  4. Subject: Re: Matrix Multiplication
  5. Message-ID: <DLqw5A.Iqy@cwi.nl>
  6. Sender: news@cwi.nl (The Daily Dross)
  7. Nntp-Posting-Host: chrysant.cwi.nl
  8. Organization: CWI, Amsterdam
  9. References: <1996Jan22.110440@gamma.ntu.ac.sg> <4e4fa7$51o@news.cencom.net>
  10. Date: Thu, 25 Jan 1996 16:22:22 GMT
  11.  
  12. In article <4e4fa7$51o@news.cencom.net> tanp@ns (Bill Wendling) writes:
  13.  > Long inexplicably wrote:
  14.  > } Dear all,
  15.  > 
  16.  > } I would like to know whether anyone of you out there has better ways to
  17.  > } do matrix multiplication (optimised for speed) in C either than using
  18.  > } two nested for loops.
  19.  > 
  20.  > Try using Gaussian Elimination to make the array have either only
  21.  > values on the diagnol or one value...Then multiply with just one for loop.
  22.  
  23. Eh?  G.E. is order n^3 the same as matrix-matrix multiplication.
  24. However, matrix-matrix multiplication requires three nested loops,
  25. matrix-vector multiplication (order n^2) requires two nested loops.
  26. For matrix-vector multiplication there is nothing better, matrix-matrix
  27. can be done better, you will find some algorithms in Knuth.  Be aware
  28. however that the algorithm by Winograd will only be faster if the
  29. elementary multiplication is much slower than the elementary addition.
  30. The algorithm trades multiplications for (more) additions/subtractions
  31. and does not really have better order.  There are other algorithms that
  32. are really better but they require in general large matrices.
  33. -- 
  34. dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924098
  35. home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/
  36.